import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 230. 二叉搜索树中第K小的元素 Kth Smallest Element In A BST
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
 */
class KthSmallestElementInABst {
    /**
     * 方法：中序遍历栈实现
     * Args:
     *     root: 二叉搜索树的根节点
     *     k: 第k小的元素
     * Returns:
     *     第k小的元素值
     * Time: O(H + k)，其中H是树的高度
     * Space: O(H)，栈空间
     */
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(--k == 0){
                break;
            }
            root = root.right;
        }
        return root.val;
    }

    /**
     * 方法：递归方式实现
     * Args:
     *     root: 二叉搜索树的根节点
     *     k: 第k小的元素
     * Returns:
     *     第k小的元素值
     * Time: O(H + k)，其中H是树的高度
     * Space: O(H)，递归栈空间
     */
    private int ans;
    private int k;
    public int kthSmallest1(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode node){
        if(node == null){
            return;
        }
        dfs(node.left);
        if(--k == 0){
            ans = node.val;
            return;
        }
        dfs(node.right);
    }
}